//
// Created by wangwanlong on 2024/7/3.
//

#ifndef MCGPP_IMSA_COARSENER_H
#define MCGPP_IMSA_COARSENER_H

#include "coarsener_base.h"
#include "vertex_pair_rater.h"
#include "sa_refiner.h"
#include "refine_info.h"
//经典的最大匹配
//重边缩合
//每一轮随机选择起点扫一边，优先选择边权重更大且没有被考虑的顶点进行缩合，否则不进行缩合
//如果有多个可以选择的：比如当前顶点有多条权重一样的边：优先选择没有被匹配的，并且找到一对匹配对立刻进行缩合
//max edge match
namespace mcgpp {

  template<class AcceptancePolicy = BestRatingOnlyUnmatched<>>
  class MemCoarnsener : public CoarsenBase {
  public:
    MemCoarnsener(ds::GenericGraph &graph) : CoarsenBase(graph),
                                             _rater(graph) {

    }

    ~MemCoarnsener() override = default;

    //不带局部搜索的纯缩合
    void coarsenImpl(int limit) override {
      int pass_iter = 0;
      _current_level_total_node_num.clear();
      _current_level_total_node_num.emplace_back(_g._current_num_nodes);

      std::vector<IDType> current_ns;
      while (_g._current_num_nodes > limit) {
        const IDType num_ns_before_pass = _g._current_num_nodes;
        for (auto v: _g._current_node_set)
          current_ns.emplace_back(v);
        Randomize::instance().shuffleVector(current_ns, current_ns.size());

        for (IDType v: current_ns) {
          if (_g.nodeIsEnabled(v)) {
            VertexPairRating rating = _rater.rate(v);
            if (rating.valid) {
              DBG << "contract " << v << " " << rating.target;
              //标记
              _rater.markAsMatched(v);
              _rater.markAsMatched(rating.target);
              //缩合
              performContraction(v, rating.target);
              _g.check();//缩合check

            }
            if (_g._current_num_nodes <= limit) {
              break;
            }
          }
          if(Timer::instance().TLE())
            break;
        }
        //本轮缩合顶点数没有变化则退出缩合
//        if (num_ns_before_pass == _g._current_num_nodes) {
//          break;
//        }
        current_ns.clear();
        _rater.resetMatches();
        ++pass_iter;
        //记录当前顶点数
        _current_level_total_node_num.emplace_back(_g._current_num_nodes);
        DBG << "part info:" << _g._part_info[0].weight << _g._part_info[1].weight;
      }
      DBG << "total pass iter:" << pass_iter;
      for (auto x: _current_level_total_node_num)
        DBG << x;
    }
    //带局部搜索的缩合
    void coarsenImpl(int limit, RefinerBase &refiner) {
      int pass_iter = 0;
      _current_level_total_node_num.clear();
      _current_level_total_node_num.emplace_back(_g._current_num_nodes);
      std::vector<IDType> current_ns;
      RefineInfo refineInfo;//记录搜索的目标值变化信息
      while (!Timer::instance().TLE() && _g._current_num_nodes > limit) {
        const IDType num_ns_before_pass = _g._current_num_nodes;
        for (auto v: _g._current_node_set)
          current_ns.emplace_back(v);
        Randomize::instance().shuffleVector(current_ns, current_ns.size());
        for (IDType v: current_ns) {
          if (_g.nodeIsEnabled(v)) {
            //1.重边打分函数
//            VertexPairRating rating = _rater.rate(v);
            //2.考虑容量打分函数
            VertexPairRating rating = _rater.rate2(v);

            if (rating.valid) {
              DBG << "contract " << v << " " << rating.target;
              //标记
              _rater.markAsMatched(v);
              _rater.markAsMatched(rating.target);
              //缩合
              performContraction(v, rating.target);
            }
//            if (_g._current_num_nodes <= limit) {
//              break;
//            }
          }
        }
        //本轮缩合顶点数没有变化则退出缩合
        if (num_ns_before_pass == _g._current_num_nodes) {
          break;
        }
        current_ns.clear();
        _rater.resetMatches();
        ++pass_iter;
        //记录当前顶点数
        _current_level_total_node_num.emplace_back(_g._current_num_nodes);
        DBG << "part info:" << _g._part_info[0].weight << _g._part_info[1].weight;
        //局部搜索
        refiner.initializeImpl();
        refineInfo.before_refine_obj = refiner.current_obj.conductance / 1e10;
        double before_true_obj = refiner.getTrueObj();
        refiner.refineImpl();

        refineInfo.after_refine_obj = refiner.current_obj.conductance / 1e10;
        double after_true_obj = refiner.getTrueObj();
        int cur_level = _current_level_total_node_num.end() - _current_level_total_node_num.begin();
        refineInfo.impove = refineInfo.after_refine_obj < refineInfo.before_refine_obj ? 1 : 0;
        LOG
        << "level:" << cur_level << "nodeNum:" << _g._current_num_nodes << refineInfo.before_refine_obj
        << refineInfo.after_refine_obj << refineInfo.impove;
        LOG<<std::fixed<<std::setprecision(10)<<before_true_obj<<after_true_obj;
      }

    }


    //带局部搜索的缩合:sa + ta
    void coarsenImpl(int limit, RefinerBase &refiner1,RefinerBase &refiner2) {
      int pass_iter = 0;
      _current_level_total_node_num.clear();
      _current_level_total_node_num.emplace_back(_g._current_num_nodes);
      std::vector<IDType> current_ns;
      RefineInfo refineInfo;//记录搜索的目标值变化信息
      while (!Timer::instance().TLE() && _g._current_num_nodes > limit) {
        const IDType num_ns_before_pass = _g._current_num_nodes;
        for (auto v: _g._current_node_set)
          current_ns.emplace_back(v);
        Randomize::instance().shuffleVector(current_ns, current_ns.size());
        for (IDType v: current_ns) {
          if (_g.nodeIsEnabled(v)) {
            VertexPairRating rating = _rater.rate(v);//重边
            if (rating.valid) {
              DBG << "contract " << v << " " << rating.target;
              //标记
              _rater.markAsMatched(v);
              _rater.markAsMatched(rating.target);
              //缩合
              performContraction(v, rating.target);
            }
//            if (_g._current_num_nodes <= limit) {
//              break;
//            }
          }
        }
        //本轮缩合顶点数没有变化则退出缩合
        if (num_ns_before_pass == _g._current_num_nodes) {
          break;
        }
        current_ns.clear();
        _rater.resetMatches();
        ++pass_iter;
        //记录当前顶点数
        _current_level_total_node_num.emplace_back(_g._current_num_nodes);
        DBG << "part info:" << _g._part_info[0].weight << _g._part_info[1].weight;
        //SA局部搜索
        refiner1.initializeImpl();
        refineInfo.before_refine_obj = refiner1.current_obj.conductance / 1e10;
        double before_true_obj = refiner1.getTrueObj();
        refiner1.refineImpl();

        //TA
        refiner2.initializeImpl();
        refineInfo.before_refine_obj = refiner2.current_obj.conductance / 1e10;
        refiner2.refineImpl();
        refineInfo.after_refine_obj = refiner2.current_obj.conductance / 1e10;
        double after_true_obj = refiner2.getTrueObj();

        int cur_level = _current_level_total_node_num.end() - _current_level_total_node_num.begin();
        refineInfo.impove = refineInfo.after_refine_obj < refineInfo.before_refine_obj ? 1 : 0;
        LOG
        << "level:" << cur_level << "nodeNum:" << _g._current_num_nodes << refineInfo.before_refine_obj
        << refineInfo.after_refine_obj << refineInfo.impove;
        LOG<<std::fixed<<std::setprecision(10)<<before_true_obj<<after_true_obj;
      }

    }

    void uncoarsenImpl(RefinerBase &refiner1,RefinerBase &refiner2) {
      //do nothing
      int level = 0;
      //局部搜索
      std::vector<IDType> refine_nodes;
      RefineInfo refineInfo;//记录搜索的目标值变化信息
      while (!_history.empty()) {
        if(Timer::instance().TLE()){
          //到时间了
          while (!_history.empty())
            performUncontraction();

          metrics::conductance(_g,refiner2.current_obj);

          break;
        }
        //还原到下一个阶段
        _current_level_total_node_num.pop_back();
        while (_g._current_num_nodes < _current_level_total_node_num.back())
          performUncontraction();

        //局部搜索
        //SA局部搜索
        refiner1.initializeImpl();
        refineInfo.before_refine_obj = refiner1.current_obj.conductance / 1e10;
        double before_true_obj = refiner1.getTrueObj();
        refiner1.refineImpl();

        //TA
        refiner2.initializeImpl();
        refineInfo.before_refine_obj = refiner2.current_obj.conductance / 1e10;
        refiner2.refineImpl();
        refineInfo.after_refine_obj = refiner2.current_obj.conductance / 1e10;
        double after_true_obj = refiner2.getTrueObj();

        int cur_level = _current_level_total_node_num.end() - _current_level_total_node_num.begin();
        refineInfo.impove = refineInfo.after_refine_obj < refineInfo.before_refine_obj ? 1 : 0;
        LOG
        << "level:" << cur_level << "nodeNum:" << _g._current_num_nodes << refineInfo.before_refine_obj
        << refineInfo.after_refine_obj << refineInfo.impove;
        LOG<<before_true_obj<<after_true_obj;
      }


    }
    void uncoarsenImpl(RefinerBase &refiner) override {
      //do nothing
      int level = 0;
      //局部搜索
      std::vector<IDType> refine_nodes;
      RefineInfo refineInfo;//记录搜索的目标值变化信息
      while (!_history.empty()) {
        if(Timer::instance().TLE()){
          //到时间了
          while (!_history.empty())
            performUncontraction();
          break;
        }
        //还原到下一个阶段
        _current_level_total_node_num.pop_back();
        while (_g._current_num_nodes < _current_level_total_node_num.back())
          performUncontraction();

        //局部搜索
        refiner.initializeImpl();
        refineInfo.before_refine_obj = refiner.current_obj.conductance / 1e10;
        double before_true_obj = refiner.getTrueObj();
        refiner.refineImpl();
        refineInfo.after_refine_obj = refiner.current_obj.conductance / 1e10;
        double after_true_obj = refiner.getTrueObj();

        int cur_level = _current_level_total_node_num.end() - _current_level_total_node_num.begin();
        refineInfo.impove = refineInfo.after_refine_obj < refineInfo.before_refine_obj ? 1 : 0;
        LOG
        << "level:" << cur_level << "nodeNum:" << _g._current_num_nodes << refineInfo.before_refine_obj
        << refineInfo.after_refine_obj << refineInfo.impove;
        LOG<<before_true_obj<<after_true_obj;
      }


    }

    void uncoarsenImpl() {

      while (!_history.empty()) {
        //还原到下一个阶段
        _current_level_total_node_num.pop_back();
        while (_g._current_num_nodes < _current_level_total_node_num.back()) {
          DBG<<"uncontract"<<_history.back().contraction_memento.u<<_history.back().contraction_memento.v;
          performUncontraction();

          _g.check();

        }
        DBG << "part info:" << _g._part_info[0].weight << _g._part_info[1].weight;
        //
        DBG << "obj:" << metrics::conductance(_g);
      }
    }

    VertexPairRater<AcceptancePolicy> _rater; // 管理打分操作
  };

}
#endif //MCGPP_IMSA_COARSENER_H
